package Offer53_34;

import java.util.Scanner;

/**
 * 在排序数组中查找数字 I
 * @author 23737
 * @create 2021.9.6
 */
public class Test {
    public static void main(String[] args){
        int[] nums = new int[]{5,7,7,8,8,10};
        int a = new Scanner(System.in).nextInt();
        int search = new Solution_Three().search(nums, 8);
        System.out.println(search);
    }
}

/*题解一：最简单的方式，遍历数组来判断*/
class Solution_53 {
    public int search(int[] nums, int target) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                count++;
            }
        }
        return count;
    }
}

/*二分查找法*/
class Solution_two{
    public int search(int[] nums, int target) {
        if(nums == null ||nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target)
            return 0;
        int left = 0;
        int right = nums.length - 1;
        while(nums[right] > target) right--;
        while(nums[left] < target) left++;
        if(left > right) return 0;
        return right - left + 1;
    }
}

/*二分查找法(官方题解)*/
class Solution_Three{
        public int search(int[] nums, int target) {
            // 搜索右边界 right
            int i = 0, j = nums.length - 1;
            while(i <= j) {
                int m = (i + j) / 2;
                if(nums[m] <= target) i = m + 1;
                else j = m - 1;
            }
            int right = i;
            // 若数组中无 target ，则提前返回
            if(j >= 0 && nums[j] != target) return 0;
            // 搜索左边界 left
            i = 0; j = nums.length - 1;
            while(i <= j) {
                int m = (i + j) / 2;
                if(nums[m] < target) i = m + 1;
                else j = m - 1;
            }
            int left = j;
            return right - left - 1;
        }
}



